BOJ_2696_중앙값 구하기

부분 정렬을 사용해서 푸는 구현 문제
홀수 인덱스마다 출력하기 때문에, 값을 배열에 추가하고 정렬해 중앙에 있는 값을 구했다

하지만 이렇게 풀면 비효율적이고, 답을 보니 Priority Queue를 활용해 푸는 방식이 더 효율적이라고 한다

해서~ 우선순위 큐로도 풀어보았다

중앙값 기준 작은 값들을 정렬할 큐, 큰 값들을 정렬할 큐를 준비한다
여기까진 모든 풀이가 동일하고, 구현에서 조금씩 차이가 있었다

내가 선택한 건 중앙값(작은 수 큐 peek()을 중앙값으로 뒀다)보다 크면 큰 수 큐에 넣고
아니면 작은 수 큐에 넣은 다음,

작은 수 큐 - 큰 수 큐 차가 1(중앙값이 작은 수 큐에 있기 때문에)보다 많이 나거나
큰 수 큐 > 작은 수 큐라면 pop()해서 다른 큐에 넣어주는 작업을 하면 된다

비교

위에 3개가 우선순위 큐로 풀어본 것이고, 맨 아래가 정렬로 푼 거다. 테스트 케이스의 크기가 별로 크지 않았는지 별 차이는 없었다. 그리고 정렬 로직이 2씩 건너 뛰며 탐색하기 때문에 더 차이가 적은 모양이다.

하지만 숫자가 크다면 큐로 구현하는 방식은 O(n log n)
정렬로 구현하는 방식은 O(n^2 * log n) 이기 때문에 우선순위 큐를 사용하는 것이 좋다

정렬 사용

T = int(input())  
  
for i in range(T):  
    M = int(input())  
    n = [0]  
    iter_range = (M + 9) // 10 if M >= 10 else 1  
    for j in range(iter_range):  
        n.extend(list(map(int, input().split())))  
  
    length = len(n)  
    n_part = []  
    print(length // 2)  
  
    for j in range(1, length, 2):  
        if j > 1:  
            n_part.append(n[j - 1])  
        n_part.append(n[j])  
  
        n_part.sort()  
        print(n_part[j // 2], end=' ')  
        if (j+1) % 20 == 0:  
            print('')  
  
    print('')

우선순위 큐 사용

from heapq import heappush, heappop  
  
T = int(input())  
  
for i in range(T):  
    # 입력  
    M = int(input())  
    n = []  
    iter_range = (M + 9) // 10 if M >= 10 else 1  
    for j in range(iter_range):  
        n.extend(list(map(int, input().split())))  
  
    # 최대힙큐, 최소힙큐 만들기  
    max_hq = list()  # 중앙값보다 작은 값들의 큐, 내림차순  
    min_hq = list()  # 중앙값보다 큰 값들의 큐, 오름차순  
    heappush(max_hq, -n[0])  
  
    print(M - M // 2)  
    print(n[0], end=' ')  
  
    for i in range(1, M):  
        if -max_hq[0] < n[i]:  
            heappush(min_hq, n[i])  
  
        else:  
            heappush(max_hq, -n[i])  
  
        if len(max_hq) - len(min_hq) > 1:  
            heappush(min_hq, -heappop(max_hq))  
  
        elif len(min_hq) - len(max_hq) > 0:  
            heappush(max_hq, -heappop(min_hq))  
  
        if i % 2 == 0:  
            print(-max_hq[0], end=' ')  
  
        if (i + 1) % 20 == 0:  
            print('')  
  
    print('')